// https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/

// 算法思路总结：
// 1. 广度优先搜索寻找迷宫中最近的出口
// 2. 从入口开始BFS，按层扩展搜索
// 3. 出口条件：边界位置且不是入口点
// 4. 使用vis数组记录访问状态，避免重复访问
// 5. 步数统计：每处理完一层，步数+1
// 6. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    typedef pair<int, int> PII;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    bool vis[101][101];
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) 
    {
        int m = maze.size();
        int n = maze[0].size();
        memset(vis, 0, sizeof(vis));

        int step = 0;
        queue<PII> q;
        q.push({entrance[0], entrance[1]});
        vis[entrance[0]][entrance[1]] = true;

        while (!q.empty())
        {
            int sz = q.size();
            for (int i = 0 ; i < sz ; i++)
            {
                auto [a, b] = q.front();
                q.pop();

                if ((a != entrance[0] || b != entrance[1]) && (a == 0 || b == 0 || a == m - 1 || b == n - 1))
                    return step;

                for (int i = 0 ; i < 4 ; i++)
                {
                    int x = a + dx[i], y = b + dy[i];
                    if (x >= 0 && y >= 0 && x < m && y < n && vis[x][y] == false && maze[x][y] == '.')
                    {
                        q.push({x, y});
                        vis[x][y] = true;
                    }
                }
            }
            step++;
        }
        return -1;
    }
};

int main()
{
    vector<vector<char>> maze1 = {
        {'+', '+', '.', '+'},
        {'.', '.', '.', '+'},
        {'+', '+', '+', '.'}
    };
    vector<int> entrance1 = {1, 2};
    
    vector<vector<char>> maze2 = {
        {'+', '+', '+'},
        {'.', '.', '.'},
        {'+', '+', '+'}
    };
    vector<int> entrance2 = {1, 0};

    Solution sol;

    cout << sol.nearestExit(maze1, entrance1) << endl;
    cout << sol.nearestExit(maze2, entrance2) << endl;

    return 0;
}